package com.lecture.java8.graph.demo01;//package com.lecture.java8.graph.demo01;
//
//import java.util.*;
//
//public class Graph {
//    private Map<Integer, Village> villages = new HashMap<>();
//    private Map<Integer, List<Road>> adjacencyList = new HashMap<>();
//
//    public void addVillage(int id, String name, int x, int y, String description) {
//        Village village = new Village(id, name, x, y, description);
//        villages.put(id, village);
//        adjacencyList.putIfAbsent(id, new ArrayList<>());
//    }
//
//    public void addRoad(int start, int end) {
//        if (!villages.containsKey(start) || !villages.containsKey(end)) return;
//        int distance = (int) Math.round(Math.sqrt(Math.pow(villages.get(start).x - villages.get(end).x, 2)
//                + Math.pow(villages.get(start).y - villages.get(end).y, 2)));
//        Road road = new Road(start, end, distance);
//        adjacencyList.get(start).add(road);
//        adjacencyList.get(end).add(new Road(end, start, distance));
//    }
//
//    public boolean isConnected() {
//        if (villages.isEmpty()) return false;
//        Set<Integer> visited = new HashSet<>();
//        int start = villages.keySet().iterator().next();
//        dfs(start, visited);
//        return visited.size() == villages.size();
//    }
//
//    private void dfs(int node, Set<Integer> visited) {
//        if (visited.contains(node)) return;
//        visited.add(node);
//        for (Road road : adjacencyList.getOrDefault(node, new ArrayList<>())) {
//            dfs(road.endId, visited);
//        }
//    }
//
//    public List<Integer> findMinimumSpanningTree() {
//        if (!isConnected()) return Collections.emptyList();
//        Set<Integer> visited = new HashSet<>();
//        PriorityQueue<Road> pq = new PriorityQueue<>(Comparator.comparingInt(r -> r.distance));
//        List<Integer> mst = new ArrayList<>();
//        int start = villages.keySet().iterator().next();
//        visited.add(start);
//        pq.addAll(adjacencyList.get(start));
//
//        while (!pq.isEmpty() && visited.size() < villages.size()) {
//            Road road = pq.poll();
//            if (visited.contains(road.end)) continue;
//            visited.add(road.end);
//            mst.add(road.end);
//            pq.addAll(adjacencyList.get(road.end));
//        }
//        return mst;
//    }
//
//    public List<Integer> findShortestPath(int start, int end) {
//        Map<Integer, Integer> distances = new HashMap<>();
//        Map<Integer, Integer> previous = new HashMap<>();
//        PriorityQueue<Road> pq = new PriorityQueue<>(Comparator.comparingInt(r -> r.startId));
//
//        distances.put(start, 0);
//        pq.add(new Road(start, start, 0));
//
//        while (!pq.isEmpty()) {
//            Road road = pq.poll();
//            int current = road.endId;
//            if (current == end) break;
//            for (Road neighbor : adjacencyList.getOrDefault(current, new ArrayList<>())) {
//                int newDist = distances.getOrDefault(current, Integer.MAX_VALUE) + neighbor.startId;
//                if (newDist < distances.getOrDefault(neighbor.endId, Integer.MAX_VALUE)) {
//                    distances.put(neighbor.endId, newDist);
//                    previous.put(neighbor.endId, current);
//                    pq.add(new Road(current, neighbor.endId, newDist));
//                }
//            }
//        }
//
//        List<Integer> path = new ArrayList<>();
//        for (Integer at = end; at != null; at = previous.get(at)) {
//            path.add(at);
//        }
//        Collections.reverse(path);
//        return path;
//    }
//}
